package com.colter.project.data.structure.sort;

import java.util.Arrays;
import java.util.Random;

public class MergeSort2 {
	public static void main(String[] args) {
		Random random = new Random();
		int[] nums = new int[10];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = random.nextInt(100);
		}

		System.out.println(Arrays.toString(nums));

		int[] result = sort(nums);
		System.out.println(Arrays.toString(result));

	}

	public static int[] sort(int[] nums) {
		if (nums.length < 2) {
			return nums;
		}
		int middle = nums.length % 2 == 0 ? nums.length / 2 : (nums.length - 1) / 2;
		int[] left = Arrays.copyOfRange(nums, 0, middle);
		int[] right = Arrays.copyOfRange(nums, middle, nums.length);

		int[] lleft = sort(left);
		int[] lright = sort(right);
		return merge(lleft, lright);
	}

	public static int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		int i = 0;
		int j = 0;
		int c = 0;

		while (i < left.length && j < right.length) {
			if (left[i] < right[j]) {
				result[c++] = right[j++];
			} else {
				result[c++] = left[i++];
			}
		}

		while (i < left.length) {
			result[c++] = left[i++];
		}
		while (j < right.length) {
			result[c++] = right[j++];
		}

		return result;
	}
}
